package com.ycy.leetcode.offer;

import com.ycy.leetcode.tree.TreeNode;
import org.junit.Test;

import java.util.LinkedList;
import java.util.List;

public class Offer34 {

  @Test
  public void test() {
    /**
     *     1
     *  2     3
     * 4 5    7 8
     *    9
     */
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.left.right.right = new TreeNode(9);

    root.right = new TreeNode(3);
    root.right.left = new TreeNode(7);
    root.right.right = new TreeNode(8);
    List<List<Integer>> lists = pathSum(root, 7);
    for (List<Integer> list : lists) {
      for (Integer integer : list) {
        System.out.print(integer + ",");
      }
      System.out.println();
    }
  }

  public List<List<Integer>> pathSum(TreeNode root, int target) {
    List<List<Integer>> res  = new LinkedList<List<Integer>>();
    LinkedList<Integer> qe = new LinkedList<Integer>();
    rec(res,qe,root,target);
    return res;
  }

  public void rec(List<List<Integer>> res,LinkedList<Integer> qe,TreeNode root, int target){
    if(root == null) return;
    qe.add(root.val);
    int sum = sum(qe);
    if( sum == target ){
      addNew(res,qe);
      qe.removeLast();
      return ;
    }else if(sum > target){
      qe.removeLast();
      return;
    }

    rec(res,qe,root.left,target);
    rec(res,qe,root.right,target);
    qe.removeLast();
  }

  public void addNew(List<List<Integer>> res,LinkedList<Integer> qe){
    List<Integer> newL = new LinkedList<>();
    for (Integer integer : qe) {
      newL.add(integer);
    }
    res.add(newL);
  }

  public int sum(List<Integer> list){
    int sum = 0;
    for(int i = 0;i<list.size();i++){
      sum += list.get(i);
    }
    return sum;
  }

}
